package datastructure;

import java.util.PriorityQueue;

public class Huffman {

	PriorityQueue<Node> queue;

	static class Node implements Comparable<Node> {
		int id;
		int freq;
		Node left, right;

		public Node(int id, int freq) {
			this.id = id;
			this.freq = freq;
		}

		@Override
		public int compareTo(Node o) {
			if (freq == o.freq)
				return 0;
			return freq > o.freq ? 1 : -1;
		}
	}

	public Node huffman(Node[] nodes) {
		int n = nodes.length;
		queue = new PriorityQueue<Node>();
		for (int i = 0; i < n; ++i) {
			queue.add(nodes[i]);
		}
		Node left, right, newNode;
		while (queue.size() > 1) {
			left = queue.poll();
			right = queue.poll();
			newNode = new Node(-1, left.freq + right.freq);
			newNode.left = left;
			newNode.right = right;
			queue.add(newNode);
		}
		return queue.poll();
	}

}
